{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_fs(graph, start, destination, strategy):   \n",
    "#    need_visit = [start]    \n",
    "    pathes = [[start]]\n",
    "    \n",
    "    seen = set()\n",
    "    \n",
    "    visited_cities = []\n",
    "    \n",
    "#    while need_visit:\n",
    "    while pathes:\n",
    "        path = pathes.pop(0)\n",
    "        \n",
    "#        froniter = need_visit.pop(0)\n",
    "        froniter = path[-1]\n",
    "        \n",
    "        if froniter in seen: continue\n",
    "        \n",
    "        for successor in graph[froniter]:\n",
    "            if successor in path: continue\n",
    "            \n",
    "            new_path = path + [successor]\n",
    "            \n",
    "            if successor == destination: # 找到目的地的时候\n",
    "                visited_cities.append(froniter)\n",
    "                visited_cities.append(successor)\n",
    "                return new_path, visited_cities, pathes # 返回了\n",
    "                \n",
    "            pathes.append(new_path)\n",
    "        \n",
    "        seen.add(froniter)\n",
    "        \n",
    "        visited_cities.append(froniter)\n",
    "        \n",
    "        pathes = sorted(pathes, key=strategy)\n",
    "    \n",
    "    return seen, visited_cities, pathes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def depth_first_search(graph, start, destination):   \n",
    "#    need_visit = [start]    \n",
    "    pathes = [[start]]\n",
    "    \n",
    "    seen = set()\n",
    "    \n",
    "    visited_cities = []\n",
    "    \n",
    "#    while need_visit:\n",
    "    while pathes:\n",
    "  #      path = pathes.pop(0) # 把以前的老路先走完\n",
    "        path = pathes.pop(-1) # 取最新的路径\n",
    "        \n",
    "#        froniter = need_visit.pop(0)\n",
    "        froniter = path[-1]\n",
    "        \n",
    "        if froniter in seen: continue\n",
    "        \n",
    "        for successor in graph[froniter]:\n",
    "            if successor in path: continue\n",
    "            \n",
    "            new_path = path + [successor]\n",
    "            \n",
    "            if successor == destination: # 找到目的地的时候\n",
    "                visited_cities.append(froniter)\n",
    "                visited_cities.append(successor)\n",
    "                return new_path, visited_cities, pathes # 返回了\n",
    "                \n",
    "            pathes.append(new_path)\n",
    "        \n",
    "        seen.add(froniter)\n",
    "        \n",
    "        visited_cities.append(froniter)\n",
    "    \n",
    "    return seen, visited_cities, pathes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['http://ditie.mapbar.com/beijing/line_ditiebatongxian/', 'http://ditie.mapbar.com/beijing/line_ditiechangpingxian/', 'http://ditie.mapbar.com/beijing/line_ditiefangshanxian/', 'http://ditie.mapbar.com/beijing/line_ditieyizhuangxian/', 'http://ditie.mapbar.com/beijing/line_jichangkuaigui/', 'http://ditie.mapbar.com/beijing/line_ditie1haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie2haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie4haoxiandaxingxian/', 'http://ditie.mapbar.com/beijing/line_ditie5haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie6haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie7haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie8haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie9haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie10haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie13haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie14haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie14haoxiandongduan/', 'http://ditie.mapbar.com/beijing/line_ditie15haoxian/', 'http://ditie.mapbar.com/beijing/line_ditie16haoxian/']\n",
      "['四惠站', '四惠东站', '高碑店站', '传媒大学站', '双桥站', '管庄站', '八里桥站', '通州北苑站', '果园站', '九棵树站', '梨园站', '临河里站', '土桥站']\n",
      "['西二旗站', '生命科学园站', '巩华城站', '沙河站', '沙河高教园站', '南邵站', '北邵洼站', '昌平东关站', '昌平站', '十三陵景区站', '昌平西山口站']\n",
      "['苏庄站', '良乡南关站', '良乡大学城西站', '良乡大学城站', '良乡大学城北站', '广阳城站', '篱笆房站', '长阳站', '稻田站', '大葆台站', '郭公庄站']\n",
      "['宋家庄站', '肖村站', '小红门站', '旧宫站', '亦庄桥站', '亦庄文化园站', '万源街站', '荣京东街站', '荣昌东街站', '同济南路站', '经海路站', '次渠南站', '次渠站']\n",
      "['东直门站', '三元桥站', '三号航站楼站', '二号航站楼站', '三元桥站', '东直门站']\n",
      "['苹果园站', '古城站', '八角游乐园站', '八宝山站', '玉泉路站', '万寿路站', '公主坟站', '军事博物馆站', '木樨地站', '南礼士路站', '复兴门站', '西单站', '天安门西站', '天安门东站', '王府井站', '东单站', '建国门站', '永安里站', '国贸站', '大望路站', '四惠站', '四惠东站']\n",
      "['积水潭站', '鼓楼大街站', '安定门站', '雍和宫站', '东直门站', '东四十条站', '朝阳门站', '建国门站', '北京站', '崇文门站', '前门站', '和平门站', '宣武门站', '长椿街站', '复兴门站', '阜成门站', '车公庄站', '西直门站', '积水潭站']\n",
      "['安河桥北站', '北宫门站', '西苑站', '圆明园站', '北京大学东门站', '中关村站', '海淀黄庄站', '人民大学站', '魏公村站', '动物园站', '西直门站', '新街口站', '平安里站', '西四站', '灵境胡同站', '西单站', '宣武门站', '菜市口站', '陶然亭站', '北京南站', '马家堡站', '角门西站', '公益西桥站', '新宫站', '西红门站', '高米店北站', '高米店南站', '枣园站', '清源路站', '黄村西大街站', '黄村火车站', '义和庄站', '生物医药基地站', '天宫院站']\n",
      "['天通苑北站', '天通苑站', '天通苑南站', '立水桥站', '立水桥南站', '北苑路北站', '大屯路东站', '惠新西街北口站', '惠新西街南口站', '和平西桥站', '和平里北街站', '雍和宫站', '北新桥站', '张自忠路站', '东四站', '灯市口站', '东单站', '崇文门站', '磁器口站', '天坛东门站', '蒲黄榆站', '刘家窑站', '宋家庄站']\n",
      "['海淀五路居站', '慈寿寺站', '花园桥站', '白石桥南站', '车公庄西站', '车公庄站', '平安里站', '北海北站', '南锣鼓巷站', '东四站', '朝阳门站', '东大桥站', '呼家楼站', '金台路站', '十里堡站', '青年路站', '褡裢坡站', '黄渠站', '常营站', '草房站', '物资学院路站', '通州北关站', '北运河西站', '郝家府站', '东夏园站', '潞城站']\n",
      "['北京西站', '广安门内站', '菜市口站', '虎坊桥站', '珠市口站', '磁器口站', '广渠门内站', '广渠门外站', '大郊亭站', '化工站', '南楼梓庄站', '欢乐谷景区站', '双合站', '焦化厂站']\n",
      "['南锣鼓巷站', '什刹海站', '鼓楼大街站', '安华桥站', '北土城站', '奥体中心站', '奥林匹克公园站', '森林公园南门站', '林萃桥站', '永泰庄站', '西小口站', '育新站', '霍营站', '平西府站', '育知路站']\n",
      "['郭公庄站', '丰台科技园站', '科怡路站', '丰台南路站', '丰台东大街站', '七里庄站', '六里桥站', '六里桥东站', '北京西站', '军事博物馆站', '白堆子站', '白石桥南站']\n",
      "['车道沟站', '长春桥站', '火器营站', '巴沟站', '苏州街站', '海淀黄庄站', '知春里站', '知春路站', '西土城站', '牡丹园站', '北土城站', '安贞门站', '惠新西街南口站', '芍药居站', '太阳宫站', '三元桥站', '亮马桥站', '农业展览馆站', '团结湖站', '呼家楼站', '金台夕照站', '国贸站', '双井站', '潘家园站', '十里河站', '分钟寺站', '成寿寺站', '宋家庄站', '石榴庄站', '大红门站', '角门东站', '角门西站', '草桥站', '纪家庙站', '首经贸站', '丰台站', '泥洼站', '西局站', '六里桥站', '莲花桥站', '公主坟站', '西钓鱼台站', '慈寿寺站', '车道沟站']\n",
      "['西直门站', '大钟寺站', '知春路站', '五道口站', '上地站', '西二旗站', '霍营站', '立水桥站', '北苑站', '望京西站', '芍药居站', '光熙门站', '柳芳站', '东直门站']\n",
      "['张郭庄站', '园博园站', '大瓦窑站', '郭庄子站', '大井站', '七里庄站', '西局站']\n",
      "['北京南站', '永定门站', '景泰站', '蒲黄榆站', '方庄站', '十里河站', '南八里庄站', '北工大西门站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '东湖渠站', '来广营站', '善各庄站']\n",
      "['清华东路西口站', '六道口站', '北沙滩站', '奥林匹克公园站', '安立路站', '大屯路东站', '关庄站', '望京西站', '望京站', '望京东站', '崔各庄站', '马泉营站', '孙河站', '国展站', '花梨坎站', '后沙峪站', '南法信站', '石门站', '顺义站', '俸伯站']\n",
      "['北安河站', '温阳路站', '稻香湖站', '屯佃站', '永丰站', '永丰南站', '西北旺站', '马连洼站', '西苑站']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {'四惠站': ['四惠东站', '大望路站', '四惠东站'],\n",
       "             '四惠东站': ['四惠站', '高碑店站', '四惠站'],\n",
       "             '高碑店站': ['四惠东站', '传媒大学站'],\n",
       "             '传媒大学站': ['高碑店站', '双桥站'],\n",
       "             '双桥站': ['传媒大学站', '管庄站'],\n",
       "             '管庄站': ['双桥站', '八里桥站'],\n",
       "             '八里桥站': ['管庄站', '通州北苑站'],\n",
       "             '通州北苑站': ['八里桥站', '果园站'],\n",
       "             '果园站': ['通州北苑站', '九棵树站'],\n",
       "             '九棵树站': ['果园站', '梨园站'],\n",
       "             '梨园站': ['九棵树站', '临河里站'],\n",
       "             '临河里站': ['梨园站', '土桥站'],\n",
       "             '土桥站': ['临河里站'],\n",
       "             '西二旗站': ['生命科学园站', '上地站', '霍营站'],\n",
       "             '生命科学园站': ['西二旗站', '巩华城站'],\n",
       "             '巩华城站': ['生命科学园站', '沙河站'],\n",
       "             '沙河站': ['巩华城站', '沙河高教园站'],\n",
       "             '沙河高教园站': ['沙河站', '南邵站'],\n",
       "             '南邵站': ['沙河高教园站', '北邵洼站'],\n",
       "             '北邵洼站': ['南邵站', '昌平东关站'],\n",
       "             '昌平东关站': ['北邵洼站', '昌平站'],\n",
       "             '昌平站': ['昌平东关站', '十三陵景区站'],\n",
       "             '十三陵景区站': ['昌平站', '昌平西山口站'],\n",
       "             '昌平西山口站': ['十三陵景区站'],\n",
       "             '苏庄站': ['良乡南关站'],\n",
       "             '良乡南关站': ['苏庄站', '良乡大学城西站'],\n",
       "             '良乡大学城西站': ['良乡南关站', '良乡大学城站'],\n",
       "             '良乡大学城站': ['良乡大学城西站', '良乡大学城北站'],\n",
       "             '良乡大学城北站': ['良乡大学城站', '广阳城站'],\n",
       "             '广阳城站': ['良乡大学城北站', '篱笆房站'],\n",
       "             '篱笆房站': ['广阳城站', '长阳站'],\n",
       "             '长阳站': ['篱笆房站', '稻田站'],\n",
       "             '稻田站': ['长阳站', '大葆台站'],\n",
       "             '大葆台站': ['稻田站', '郭公庄站'],\n",
       "             '郭公庄站': ['大葆台站', '丰台科技园站'],\n",
       "             '宋家庄站': ['肖村站', '刘家窑站', '成寿寺站', '石榴庄站'],\n",
       "             '肖村站': ['宋家庄站', '小红门站'],\n",
       "             '小红门站': ['肖村站', '旧宫站'],\n",
       "             '旧宫站': ['小红门站', '亦庄桥站'],\n",
       "             '亦庄桥站': ['旧宫站', '亦庄文化园站'],\n",
       "             '亦庄文化园站': ['亦庄桥站', '万源街站'],\n",
       "             '万源街站': ['亦庄文化园站', '荣京东街站'],\n",
       "             '荣京东街站': ['万源街站', '荣昌东街站'],\n",
       "             '荣昌东街站': ['荣京东街站', '同济南路站'],\n",
       "             '同济南路站': ['荣昌东街站', '经海路站'],\n",
       "             '经海路站': ['同济南路站', '次渠南站'],\n",
       "             '次渠南站': ['经海路站', '次渠站'],\n",
       "             '次渠站': ['次渠南站'],\n",
       "             '东直门站': ['三元桥站', '三元桥站', '三元桥站', '三元桥站', '雍和宫站', '东四十条站', '柳芳站'],\n",
       "             '三元桥站': ['东直门站',\n",
       "              '三号航站楼站',\n",
       "              '东直门站',\n",
       "              '东直门站',\n",
       "              '三号航站楼站',\n",
       "              '东直门站',\n",
       "              '太阳宫站',\n",
       "              '亮马桥站'],\n",
       "             '三号航站楼站': ['三元桥站', '二号航站楼站', '三元桥站'],\n",
       "             '二号航站楼站': ['三号航站楼站'],\n",
       "             '苹果园站': ['古城站'],\n",
       "             '古城站': ['苹果园站', '八角游乐园站'],\n",
       "             '八角游乐园站': ['古城站', '八宝山站'],\n",
       "             '八宝山站': ['八角游乐园站', '玉泉路站'],\n",
       "             '玉泉路站': ['八宝山站', '万寿路站'],\n",
       "             '万寿路站': ['玉泉路站', '公主坟站'],\n",
       "             '公主坟站': ['万寿路站', '军事博物馆站', '莲花桥站', '西钓鱼台站'],\n",
       "             '军事博物馆站': ['公主坟站', '木樨地站', '北京西站', '白堆子站'],\n",
       "             '木樨地站': ['军事博物馆站', '南礼士路站'],\n",
       "             '南礼士路站': ['木樨地站', '复兴门站'],\n",
       "             '复兴门站': ['南礼士路站', '西单站', '长椿街站', '阜成门站'],\n",
       "             '西单站': ['复兴门站', '天安门西站', '灵境胡同站', '宣武门站'],\n",
       "             '天安门西站': ['西单站', '天安门东站'],\n",
       "             '天安门东站': ['天安门西站', '王府井站'],\n",
       "             '王府井站': ['天安门东站', '东单站'],\n",
       "             '东单站': ['王府井站', '建国门站', '灯市口站', '崇文门站'],\n",
       "             '建国门站': ['东单站', '永安里站', '朝阳门站', '北京站'],\n",
       "             '永安里站': ['建国门站', '国贸站'],\n",
       "             '国贸站': ['永安里站', '大望路站', '金台夕照站', '双井站'],\n",
       "             '大望路站': ['国贸站', '四惠站', '北工大西门站', '红庙站'],\n",
       "             '积水潭站': ['鼓楼大街站', '鼓楼大街站'],\n",
       "             '鼓楼大街站': ['积水潭站', '安定门站', '积水潭站', '什刹海站', '安华桥站'],\n",
       "             '安定门站': ['鼓楼大街站', '雍和宫站'],\n",
       "             '雍和宫站': ['安定门站', '东直门站', '和平里北街站', '北新桥站'],\n",
       "             '东四十条站': ['东直门站', '朝阳门站'],\n",
       "             '朝阳门站': ['东四十条站', '建国门站', '东四站', '东大桥站'],\n",
       "             '北京站': ['建国门站', '崇文门站'],\n",
       "             '崇文门站': ['北京站', '前门站', '东单站', '磁器口站'],\n",
       "             '前门站': ['崇文门站', '和平门站'],\n",
       "             '和平门站': ['前门站', '宣武门站'],\n",
       "             '宣武门站': ['和平门站', '长椿街站', '西单站', '菜市口站'],\n",
       "             '长椿街站': ['宣武门站', '复兴门站'],\n",
       "             '阜成门站': ['复兴门站', '车公庄站'],\n",
       "             '车公庄站': ['阜成门站', '西直门站', '车公庄西站', '平安里站'],\n",
       "             '西直门站': ['车公庄站', '动物园站', '新街口站', '大钟寺站'],\n",
       "             '安河桥北站': ['北宫门站'],\n",
       "             '北宫门站': ['安河桥北站', '西苑站'],\n",
       "             '西苑站': ['北宫门站', '圆明园站', '马连洼站'],\n",
       "             '圆明园站': ['西苑站', '北京大学东门站'],\n",
       "             '北京大学东门站': ['圆明园站', '中关村站'],\n",
       "             '中关村站': ['北京大学东门站', '海淀黄庄站'],\n",
       "             '海淀黄庄站': ['中关村站', '人民大学站', '苏州街站', '知春里站'],\n",
       "             '人民大学站': ['海淀黄庄站', '魏公村站'],\n",
       "             '魏公村站': ['人民大学站', '动物园站'],\n",
       "             '动物园站': ['魏公村站', '西直门站'],\n",
       "             '新街口站': ['西直门站', '平安里站'],\n",
       "             '平安里站': ['新街口站', '西四站', '车公庄站', '北海北站'],\n",
       "             '西四站': ['平安里站', '灵境胡同站'],\n",
       "             '灵境胡同站': ['西四站', '西单站'],\n",
       "             '菜市口站': ['宣武门站', '陶然亭站', '广安门内站', '虎坊桥站'],\n",
       "             '陶然亭站': ['菜市口站', '北京南站'],\n",
       "             '北京南站': ['陶然亭站', '马家堡站', '永定门站'],\n",
       "             '马家堡站': ['北京南站', '角门西站'],\n",
       "             '角门西站': ['马家堡站', '公益西桥站', '角门东站', '草桥站'],\n",
       "             '公益西桥站': ['角门西站', '新宫站'],\n",
       "             '新宫站': ['公益西桥站', '西红门站'],\n",
       "             '西红门站': ['新宫站', '高米店北站'],\n",
       "             '高米店北站': ['西红门站', '高米店南站'],\n",
       "             '高米店南站': ['高米店北站', '枣园站'],\n",
       "             '枣园站': ['高米店南站', '清源路站'],\n",
       "             '清源路站': ['枣园站', '黄村西大街站'],\n",
       "             '黄村西大街站': ['清源路站', '黄村火车站'],\n",
       "             '黄村火车站': ['黄村西大街站', '义和庄站'],\n",
       "             '义和庄站': ['黄村火车站', '生物医药基地站'],\n",
       "             '生物医药基地站': ['义和庄站', '天宫院站'],\n",
       "             '天宫院站': ['生物医药基地站'],\n",
       "             '天通苑北站': ['天通苑站'],\n",
       "             '天通苑站': ['天通苑北站', '天通苑南站'],\n",
       "             '天通苑南站': ['天通苑站', '立水桥站'],\n",
       "             '立水桥站': ['天通苑南站', '立水桥南站', '霍营站', '北苑站'],\n",
       "             '立水桥南站': ['立水桥站', '北苑路北站'],\n",
       "             '北苑路北站': ['立水桥南站', '大屯路东站'],\n",
       "             '大屯路东站': ['北苑路北站', '惠新西街北口站', '安立路站', '关庄站'],\n",
       "             '惠新西街北口站': ['大屯路东站', '惠新西街南口站'],\n",
       "             '惠新西街南口站': ['惠新西街北口站', '和平西桥站', '安贞门站', '芍药居站'],\n",
       "             '和平西桥站': ['惠新西街南口站', '和平里北街站'],\n",
       "             '和平里北街站': ['和平西桥站', '雍和宫站'],\n",
       "             '北新桥站': ['雍和宫站', '张自忠路站'],\n",
       "             '张自忠路站': ['北新桥站', '东四站'],\n",
       "             '东四站': ['张自忠路站', '灯市口站', '南锣鼓巷站', '朝阳门站'],\n",
       "             '灯市口站': ['东四站', '东单站'],\n",
       "             '磁器口站': ['崇文门站', '天坛东门站', '珠市口站', '广渠门内站'],\n",
       "             '天坛东门站': ['磁器口站', '蒲黄榆站'],\n",
       "             '蒲黄榆站': ['天坛东门站', '刘家窑站', '景泰站', '方庄站'],\n",
       "             '刘家窑站': ['蒲黄榆站', '宋家庄站'],\n",
       "             '海淀五路居站': ['慈寿寺站'],\n",
       "             '慈寿寺站': ['海淀五路居站', '花园桥站', '西钓鱼台站'],\n",
       "             '花园桥站': ['慈寿寺站', '白石桥南站'],\n",
       "             '白石桥南站': ['花园桥站', '车公庄西站', '白堆子站'],\n",
       "             '车公庄西站': ['白石桥南站', '车公庄站'],\n",
       "             '北海北站': ['平安里站', '南锣鼓巷站'],\n",
       "             '南锣鼓巷站': ['北海北站', '东四站', '什刹海站'],\n",
       "             '东大桥站': ['朝阳门站', '呼家楼站'],\n",
       "             '呼家楼站': ['东大桥站', '金台路站', '团结湖站', '金台夕照站'],\n",
       "             '金台路站': ['呼家楼站', '十里堡站', '红庙站', '朝阳公园站'],\n",
       "             '十里堡站': ['金台路站', '青年路站'],\n",
       "             '青年路站': ['十里堡站', '褡裢坡站'],\n",
       "             '褡裢坡站': ['青年路站', '黄渠站'],\n",
       "             '黄渠站': ['褡裢坡站', '常营站'],\n",
       "             '常营站': ['黄渠站', '草房站'],\n",
       "             '草房站': ['常营站', '物资学院路站'],\n",
       "             '物资学院路站': ['草房站', '通州北关站'],\n",
       "             '通州北关站': ['物资学院路站', '北运河西站'],\n",
       "             '北运河西站': ['通州北关站', '郝家府站'],\n",
       "             '郝家府站': ['北运河西站', '东夏园站'],\n",
       "             '东夏园站': ['郝家府站', '潞城站'],\n",
       "             '潞城站': ['东夏园站'],\n",
       "             '北京西站': ['广安门内站', '六里桥东站', '军事博物馆站'],\n",
       "             '广安门内站': ['北京西站', '菜市口站'],\n",
       "             '虎坊桥站': ['菜市口站', '珠市口站'],\n",
       "             '珠市口站': ['虎坊桥站', '磁器口站'],\n",
       "             '广渠门内站': ['磁器口站', '广渠门外站'],\n",
       "             '广渠门外站': ['广渠门内站', '大郊亭站'],\n",
       "             '大郊亭站': ['广渠门外站', '化工站'],\n",
       "             '化工站': ['大郊亭站', '南楼梓庄站'],\n",
       "             '南楼梓庄站': ['化工站', '欢乐谷景区站'],\n",
       "             '欢乐谷景区站': ['南楼梓庄站', '双合站'],\n",
       "             '双合站': ['欢乐谷景区站', '焦化厂站'],\n",
       "             '焦化厂站': ['双合站'],\n",
       "             '什刹海站': ['南锣鼓巷站', '鼓楼大街站'],\n",
       "             '安华桥站': ['鼓楼大街站', '北土城站'],\n",
       "             '北土城站': ['安华桥站', '奥体中心站', '牡丹园站', '安贞门站'],\n",
       "             '奥体中心站': ['北土城站', '奥林匹克公园站'],\n",
       "             '奥林匹克公园站': ['奥体中心站', '森林公园南门站', '北沙滩站', '安立路站'],\n",
       "             '森林公园南门站': ['奥林匹克公园站', '林萃桥站'],\n",
       "             '林萃桥站': ['森林公园南门站', '永泰庄站'],\n",
       "             '永泰庄站': ['林萃桥站', '西小口站'],\n",
       "             '西小口站': ['永泰庄站', '育新站'],\n",
       "             '育新站': ['西小口站', '霍营站'],\n",
       "             '霍营站': ['育新站', '平西府站', '西二旗站', '立水桥站'],\n",
       "             '平西府站': ['霍营站', '育知路站'],\n",
       "             '育知路站': ['平西府站'],\n",
       "             '丰台科技园站': ['郭公庄站', '科怡路站'],\n",
       "             '科怡路站': ['丰台科技园站', '丰台南路站'],\n",
       "             '丰台南路站': ['科怡路站', '丰台东大街站'],\n",
       "             '丰台东大街站': ['丰台南路站', '七里庄站'],\n",
       "             '七里庄站': ['丰台东大街站', '六里桥站', '大井站', '西局站'],\n",
       "             '六里桥站': ['七里庄站', '六里桥东站', '西局站', '莲花桥站'],\n",
       "             '六里桥东站': ['六里桥站', '北京西站'],\n",
       "             '白堆子站': ['军事博物馆站', '白石桥南站'],\n",
       "             '车道沟站': ['长春桥站', '长春桥站'],\n",
       "             '长春桥站': ['车道沟站', '火器营站', '车道沟站'],\n",
       "             '火器营站': ['长春桥站', '巴沟站'],\n",
       "             '巴沟站': ['火器营站', '苏州街站'],\n",
       "             '苏州街站': ['巴沟站', '海淀黄庄站'],\n",
       "             '知春里站': ['海淀黄庄站', '知春路站'],\n",
       "             '知春路站': ['知春里站', '西土城站', '大钟寺站', '五道口站'],\n",
       "             '西土城站': ['知春路站', '牡丹园站'],\n",
       "             '牡丹园站': ['西土城站', '北土城站'],\n",
       "             '安贞门站': ['北土城站', '惠新西街南口站'],\n",
       "             '芍药居站': ['惠新西街南口站', '太阳宫站', '望京西站', '光熙门站'],\n",
       "             '太阳宫站': ['芍药居站', '三元桥站'],\n",
       "             '亮马桥站': ['三元桥站', '农业展览馆站'],\n",
       "             '农业展览馆站': ['亮马桥站', '团结湖站'],\n",
       "             '团结湖站': ['农业展览馆站', '呼家楼站'],\n",
       "             '金台夕照站': ['呼家楼站', '国贸站'],\n",
       "             '双井站': ['国贸站', '潘家园站'],\n",
       "             '潘家园站': ['双井站', '十里河站'],\n",
       "             '十里河站': ['潘家园站', '分钟寺站', '方庄站', '南八里庄站'],\n",
       "             '分钟寺站': ['十里河站', '成寿寺站'],\n",
       "             '成寿寺站': ['分钟寺站', '宋家庄站'],\n",
       "             '石榴庄站': ['宋家庄站', '大红门站'],\n",
       "             '大红门站': ['石榴庄站', '角门东站'],\n",
       "             '角门东站': ['大红门站', '角门西站'],\n",
       "             '草桥站': ['角门西站', '纪家庙站'],\n",
       "             '纪家庙站': ['草桥站', '首经贸站'],\n",
       "             '首经贸站': ['纪家庙站', '丰台站'],\n",
       "             '丰台站': ['首经贸站', '泥洼站'],\n",
       "             '泥洼站': ['丰台站', '西局站'],\n",
       "             '西局站': ['泥洼站', '六里桥站', '七里庄站'],\n",
       "             '莲花桥站': ['六里桥站', '公主坟站'],\n",
       "             '西钓鱼台站': ['公主坟站', '慈寿寺站'],\n",
       "             '大钟寺站': ['西直门站', '知春路站'],\n",
       "             '五道口站': ['知春路站', '上地站'],\n",
       "             '上地站': ['五道口站', '西二旗站'],\n",
       "             '北苑站': ['立水桥站', '望京西站'],\n",
       "             '望京西站': ['北苑站', '芍药居站', '关庄站', '望京站'],\n",
       "             '光熙门站': ['芍药居站', '柳芳站'],\n",
       "             '柳芳站': ['光熙门站', '东直门站'],\n",
       "             '张郭庄站': ['园博园站'],\n",
       "             '园博园站': ['张郭庄站', '大瓦窑站'],\n",
       "             '大瓦窑站': ['园博园站', '郭庄子站'],\n",
       "             '郭庄子站': ['大瓦窑站', '大井站'],\n",
       "             '大井站': ['郭庄子站', '七里庄站'],\n",
       "             '永定门站': ['北京南站', '景泰站'],\n",
       "             '景泰站': ['永定门站', '蒲黄榆站'],\n",
       "             '方庄站': ['蒲黄榆站', '十里河站'],\n",
       "             '南八里庄站': ['十里河站', '北工大西门站'],\n",
       "             '北工大西门站': ['南八里庄站', '大望路站'],\n",
       "             '红庙站': ['大望路站', '金台路站'],\n",
       "             '朝阳公园站': ['金台路站', '枣营站'],\n",
       "             '枣营站': ['朝阳公园站', '东风北桥站'],\n",
       "             '东风北桥站': ['枣营站', '将台站'],\n",
       "             '将台站': ['东风北桥站', '望京南站'],\n",
       "             '望京南站': ['将台站', '阜通站'],\n",
       "             '阜通站': ['望京南站', '望京站'],\n",
       "             '望京站': ['阜通站', '东湖渠站', '望京西站', '望京东站'],\n",
       "             '东湖渠站': ['望京站', '来广营站'],\n",
       "             '来广营站': ['东湖渠站', '善各庄站'],\n",
       "             '善各庄站': ['来广营站'],\n",
       "             '清华东路西口站': ['六道口站'],\n",
       "             '六道口站': ['清华东路西口站', '北沙滩站'],\n",
       "             '北沙滩站': ['六道口站', '奥林匹克公园站'],\n",
       "             '安立路站': ['奥林匹克公园站', '大屯路东站'],\n",
       "             '关庄站': ['大屯路东站', '望京西站'],\n",
       "             '望京东站': ['望京站', '崔各庄站'],\n",
       "             '崔各庄站': ['望京东站', '马泉营站'],\n",
       "             '马泉营站': ['崔各庄站', '孙河站'],\n",
       "             '孙河站': ['马泉营站', '国展站'],\n",
       "             '国展站': ['孙河站', '花梨坎站'],\n",
       "             '花梨坎站': ['国展站', '后沙峪站'],\n",
       "             '后沙峪站': ['花梨坎站', '南法信站'],\n",
       "             '南法信站': ['后沙峪站', '石门站'],\n",
       "             '石门站': ['南法信站', '顺义站'],\n",
       "             '顺义站': ['石门站', '俸伯站'],\n",
       "             '俸伯站': ['顺义站'],\n",
       "             '北安河站': ['温阳路站'],\n",
       "             '温阳路站': ['北安河站', '稻香湖站'],\n",
       "             '稻香湖站': ['温阳路站', '屯佃站'],\n",
       "             '屯佃站': ['稻香湖站', '永丰站'],\n",
       "             '永丰站': ['屯佃站', '永丰南站'],\n",
       "             '永丰南站': ['永丰站', '西北旺站'],\n",
       "             '西北旺站': ['永丰南站', '马连洼站'],\n",
       "             '马连洼站': ['西北旺站', '西苑站']})"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import re\n",
    "import requests\n",
    "url = 'https://ditie.mapbar.com/beijing/'\n",
    "response = requests.get(url)\n",
    "pattern = \"\"\"<a href=\"(http://ditie\\.mapbar\\.com/beijing/\\w+/)\" style=\"background-color:#\\w+\" target=\"_blank\">(\\w+)</a>\"\"\"\n",
    "all_lines=re.findall(pattern, response.text)\n",
    "allLineArray = []\n",
    "for line in all_lines:\n",
    "    allLineArray.append(line[0])\n",
    "\n",
    "pattern = '<li\\s*.*><a class=\"cl\\-station\" href=\"http://ditie\\.mapbar\\.com/beijing/station_\\w+/\" target=\"_blank\" title=\"\\w+\">(\\w+)</a></li>'\n",
    "all = []\n",
    "print(allLineArray)\n",
    "for url in allLineArray:\n",
    "    response=requests.get(url)\n",
    "    everyLine=re.findall(pattern, response.text)\n",
    "    print(everyLine)\n",
    "    all.append(everyLine)\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "#想变成上面 In[76] city_connection的结果 ，此处是ditie_connection\n",
    "ditie_connection = defaultdict(list)\n",
    "for every in all:\n",
    "    for name1 in every:\n",
    "        for name2 in every:\n",
    "            if every.index(name1)==0 and every.index(name2)==1:\n",
    "                ditie_connection[name1].append(name2)\n",
    "            elif every.index(name1)==len(every)-1 and every.index(name2)==len(every)-2:\n",
    "                ditie_connection[name1].append(name2)\n",
    "            elif every.index(name1)>0 and every.index(name1)<len(every):\n",
    "                n=every.index(name1)\n",
    "                if every.index(name2)==n-1 or every.index(name2)==n+1:\n",
    "                    ditie_connection[name1].append(name2)\n",
    "\n",
    "ditie_connection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['四惠站', '大望路站', '国贸站', '永安里站', '建国门站', '东单站', '王府井站', '天安门东站', '天安门西站', '西单站', '复兴门站', '南礼士路站', '木樨地站', '军事博物馆站', '公主坟站', '西钓鱼台站', '慈寿寺站', '花园桥站', '白石桥南站', '车公庄西站', '车公庄站', '西直门站', '动物园站', '魏公村站', '人民大学站', '海淀黄庄站', '知春里站', '知春路站', '西土城站', '牡丹园站', '北土城站', '安华桥站', '鼓楼大街站', '安定门站', '雍和宫站', '东直门站', '三元桥站', '太阳宫站', '芍药居站', '惠新西街南口站', '惠新西街北口站', '大屯路东站', '北苑路北站', '立水桥南站', '立水桥站', '霍营站', '西二旗站', '生命科学园站', '巩华城站', '沙河站']\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "ditie_graph = nx.Graph(ditie_connection)\n",
    "# nx.draw(city_graph, ditie_connection, with_labels=False)\n",
    "p, v, ps = best_fs(ditie_graph, '四惠站', '沙河站', lambda x: -len(x))\n",
    "print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['四惠站', '四惠东站'], ['四惠站', '大望路站', '国贸站'], ['四惠站', '大望路站', '北工大西门站'], ['四惠站', '大望路站', '红庙站', '金台路站', '呼家楼站'], ['四惠站', '大望路站', '红庙站', '金台路站', '十里堡站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '东湖渠站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '北苑站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '芍药居站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '关庄站', '大屯路东站', '北苑路北站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '关庄站', '大屯路东站', '惠新西街北口站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '关庄站', '大屯路东站', '安立路站', '奥林匹克公园站', '奥体中心站'], ['四惠站', '大望路站', '红庙站', '金台路站', '朝阳公园站', '枣营站', '东风北桥站', '将台站', '望京南站', '阜通站', '望京站', '望京西站', '关庄站', '大屯路东站', '安立路站', '奥林匹克公园站', '森林公园南门站', '林萃桥站', '永泰庄站', '西小口站', '育新站', '霍营站', '平西府站']]\n"
     ]
    }
   ],
   "source": [
    "path, visited_dities, pathes = depth_first_search(ditie_connection, '四惠站', '沙河站')\n",
    "print(pathes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "ditie_location = {}\n",
    "for every in all:\n",
    "    for name in every:\n",
    "        ditie_location[name] = '[]'\n",
    "    \n",
    "ditie_location\n",
    "# city_graph = nx.Graph(ditie_connection)\n",
    "# nx.draw(city_graph, ditie_location, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
